import com.sun.org.apache.bcel.internal.generic.ARRAYLENGTH;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Stack;

public class TreeOperation {

    // 前序遍历
    public void pre(TreeNode root) {
        if (root == null)
            return;
        System.out.print(root.val);
        pre(root.left);
        pre(root.right);
    }

    static void preTree(TreeNode head) {
        if (head != null) {
            Stack<TreeNode> stack = new Stack<>();
            stack.add(head); // 元素入栈
            while (!stack.isEmpty()) {
                head = stack.pop(); // 元素出栈
                System.out.print(head.val + " ");
                // 先压右后压左
                if (head.right != null) {
                    stack.push(head.right);
                }
                if (head.left != null) {
                    stack.push(head.left);
                }
            }
        }
    }


    // 中序遍历
    public void cur(TreeNode root){
        if (root == null)
            return;
        cur(root.left);
        System.out.print(root.val);
        cur(root.right);
    }

    static void curTree(TreeNode head) {
        if (head != null) { // 只是判断一个数是否为空树
            Stack<TreeNode> stack = new Stack<>();
            while (!stack.isEmpty() || head != null) {
                if (head != null) {
                    stack.push(head); // 入栈
                    head = head.left;
                } else {
                    head = stack.pop(); // 出栈
                    System.out.println(head.val);
                    head = head.right;
                }
            }
        }
    }


    // 后序遍历
    public void nxt(TreeNode root){
        if (root == null)
            return;
        nxt(root.left);
        nxt(root.right);
        System.out.print(root.val);
    }

    static void searchTree4(TreeNode head) {
        if (head != null) {
            Stack<TreeNode> stack1 = new Stack<>();
            Stack<TreeNode> stack2 = new Stack<>();
            ArrayDeque<Integer> deque = new ArrayDeque<>();

            stack1.push(head);
            while (!stack1.isEmpty()) {
                head = stack1.pop();// 出栈
                stack2.push(head);	// 入栈
                // 先压左再压右
                if (head.left != null) {
                    stack1.push(head.left);
                }
                if (head.right != null) {
                    stack1.push(head.right);
                }
            }
            // 倒元素
            while (!stack2.isEmpty()) {
                System.out.print(stack2.pop().val);
            }
        }
    }

   // 层次遍历
    public void levelTraversal(TreeNode root){
       Deque<TreeNode> tree = new ArrayDeque<>();
       tree.add(root);
       while(!tree.isEmpty()){
           TreeNode tmp = tree.poll();
           tree.add(tmp.left);
           tree.add(tmp.right);
       }
    }
}

class TreeNode {
    public int val;
    TreeNode left;
    TreeNode right;

    public TreeNode() {
    }

    public TreeNode(int val) {
        this.val = val;
    }

    public TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
